Since the advent of digital images, it has been a goal of digital image processing to identify and locate features in an image. Many algorithms and methods have been developed to accomplish this goal.
A simple method of detecting target features in a scanned image is known as template correlation. Here, a representative image of the sought after target feature is formed and stored in memory. Subsequently, the representative image (or template) is stepped over the scanned image and a correlation score is calculated for each step position. A sharp peak in correlation scores indicates the presence and location of the target feature in the scanned image. This method, however, has several limitations. A chief limitation of template correlation is that it is highly sensitive to differences in size and rotation of the digital image relative to the template. So, for a robust scale and rotationally invariant detection system, multiple templates need to be formed, requiring a prohibitive level of system complexity.
Another method of detecting target features in a scanned image is performed by statistical means. Here, a machine is trained to identify target features by various machine learning algorithms. Generally, the training process involves inputting large test sets of images with and without target features. At the conclusion of the training process, a classification vector is generated by which new ‘unseen’ target features in images may be detected. However, this method is highly dependent on the test sets input during the training process. The resulting classification vector may be unpredictable, and may be unrelated to the salient features of the target feature.
Another method of detecting target features in a scanned image is simple and efficient. Here, a target feature that has a known arrangement of black and white regions may be detected by inspecting the ratios between those black and white regions. As an example, a target feature such as the feature 100 of FIG. 1 will be detected if ratios of 1 part black, followed by 1 part white, followed by 3 parts black, followed by 1 part white and finally followed by 1 part black are sought. Although this method is extremely easy and efficient to implement, it suffers when the image of the target feature is affected by a distortion effect known as dot gain. Dot gain is a printer distortion that shrinks or grows the thickness of black printed regions. This directly affects the ratios of black and white regions. Thus, this method is not suitable in the presence of dot gain.
A QR code, such as the code 300 of FIG. 3, is a two-dimensional barcode that encodes information with black and white square blocks, referred to as ‘modules’. In the QR code 300, labelled are a black module 302 and a white module 301. QR codes have a range of data capacities. A ‘Version 1’ QR code encodes the least number of data bits, and a ‘Version 40’ QR code encodes the maximum number of data bits. QR codes encoding more data bits have a greater number of modules. Irrespective of its data capacity, a QR code will always be the same number of modules in width as it is in height—that is, QR codes are always square.
A QR code comprises three location and identification symbols. These three location symbols are known as ‘finder patterns’ (FPs) and are located in the top-left, top-right, and bottom-left corners of a QR code. Therefore, the two-dimensional area of an image occupied by a QR code, also known as a ‘QR code region’, is demarcated by the locations of the three FPs. FIG. 2B shows these three FPs 201, 202, 203 as may be located at three corners of a QR code 200. FIG. 2A provides an enlarged representation of the FP 202. FIG. 1 is a detailed view of a QR code finder pattern 100. Finder patterns are composed of a 3-by-3 square of black modules 103 superimposed on a 5-by-5 square of white modules 102, which is in turn superimposed on a 7-by-7 square of black modules 101.
The process of extracting the data encoded in a QR code begins with the acquisition of an image containing the code. Subsequently, all three finder patterns are detected and their locations are determined. Using the location information of the detected FPs, data modules of the QR code are then sampled to obtain a binary data stream. Finally, the binary data stream is translated to meaningful text or numerical information.
QR codes are frequently included on a broad range of media, such as product labels, billboards and business cards. In general, these media have only included a single QR code of high quality (that is, the digital image of the original QR code has been accurately re-produced on the media). Therefore, when a QR code is being decoded, there is only a single QR code in the acquired image and the quality of the code is high, facilitating the use of relatively simple decoding processing. Furthermore, conventional QR code capturing devices (such as camera phones) can be user-adjusted such that an image of the QR code may be acquired with very little rotational misalignment. These user-adjusted capturing devices can also frame the QR code such that the size of modules in the QR code (with respect to the capturing device) is within a confined known range.
Recently, there has been increased interest in the application of QR codes in aiding document security and workflow management. For these applications, there may be multiple QR codes in an acquired image. Furthermore, there will often be a broad variation in module sizes and orientations amongst the QR codes in the image. The QR codes may also have been printed, scanned and re-printed many times, each time introducing deterioration of the QR code image quality. Specifically, QR codes may suffer from ‘dot gain’ in which the ratio of black module size and white module size in the QR code differs significantly from the ideal 1:1 ratio. Multiple cycles of printing and scanning also introduces noise and other distortions that further alter the appearance of QR code finder patterns compared to the ideal FP 100. The effect of dot gain and other print and/or scan introduced distortions on decoding reliability using traditional techniques can be considerable. This is because traditional decoding systems typically rely heavily on the expected appearance of QR code finder patterns 100, especially the 1:1 ratio between white and black module sizes, to detect the QR code finder patterns and thereby decode the QR code.